#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>

int test_case[7] = {1000, 2500, 5000, 10000, 25000, 50000, 100000};
int case_len = sizeof(test_case)/sizeof(int);

void testWQU();
void testHeightWQU();

int main(int argc, char **argv) {
    srand(time(NULL));
    testWQU();
    testHeightWQU();
    return 0;
}
// 时间获取函数（毫秒精度）
long get_time_ms() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

void testWQU(){
    printf("Weighted Quick Union\n");
    for (int k = 0; k < case_len; k++) {
        // 执行测试
        long start = get_time_ms();
        int N = test_case[k];
        int edges = 0;
        int setNum = N;
        int id[N];
        int sz[N];

        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }

        while (setNum > 1) {
            int p = rand() % N;
            int q = rand() % N;
            int i, j;
            for (i = id[p]; i != id[i]; i = id[i]) {
                ;
            }
            for (j = id[q]; j != id[j]; j = id[j]) {
                ;
            }
            if (i == j) {
                continue;
            }
            if (sz[i] < sz[j]) {
                id[i] = j;
                sz[j] += sz[i];
            }else {
                id[j] = i;
                sz[i] += sz[j];
            }
            
            setNum--;
            edges++;
        }
        long elapsed = get_time_ms() - start;
        
        printf("N = %d, M = %d, costTime = %ld\n", N, edges, elapsed);
    }
}

void testHeightWQU(){
    printf("Height Weighted Quick Union\n");
    for (int k = 0; k < case_len; k++) {
        // 执行测试
        long start = get_time_ms();
        int N = test_case[k];
        int edges = 0;
        int setNum = N;
        int id[N];
        int heigt[N];

        for (int i = 0; i < N; i++) {
            id[i] = i;
            heigt[i] = 0;
        }

        while (setNum > 1) {
            int p = rand() % N;
            int q = rand() % N;
            int i, j;
            for (i = id[p]; i != id[i]; i = id[i]) {
                ;
            }
            for (j = id[q]; j != id[j]; j = id[j]) {
                ;
            }
            if (i == j) {
                continue;
            }
            if (heigt[i] < heigt[j]) {
                id[i] = j;
            }else if (heigt[i] > heigt[j]){
                id[j] = i;
            }else {
                id[j] = i;
                heigt[i]++;
            }
            
            setNum--;
            edges++;
        }
        long elapsed = get_time_ms() - start;
        
        printf("N = %d, M = %d, costTime = %ld\n", N, edges, elapsed);
    }
}